package com.zhao.arithmetic

import scala.collection.mutable.ArrayBuffer
import scala.util.Random

/**
 * Description: 二分查找<br/>
 * Copyright (c) ，2020 ， 赵 <br/>
 * This program is protected by copyright laws. <br/>
 * Date： 2020/12/30 10:02
 * 对于一个无序的集合,查找一个元素的时间复杂度是 o(n)
 * 二分查找适应于有序的查找元素,时间复杂度是 o(logn)
 *
 * @author 柒柒
 * @version : 1.0
 */

object BinarySearch {
  def main(args: Array[String]): Unit = {

    //进行二分查找的前提是有序,默认升序
    val arr: Array[Int] = Array(1, 8, 10, 89, 1000, 1000, 1000, 1000, 1234)
    //    val index = binarySearch(arr, 0, arr.length, 89)
    //    if (index != -1){
    //      println("找到了,下标为:"+index)
    //    }else{
    //      println("没有找到")
    //    }
    val resArr: ArrayBuffer[Int] = binarySearch2(arr, 0, arr.length, 1000)
    resArr.sortBy((x:Int) =>x)
    if (resArr.length != 0){
      for (index <- resArr){
        println("找到的索引有:"+index)
      }
    }else{
      println("没有找到")
    }
  }

  def setValue(arr: Array[Int],num:Int) = {
    for (i <- 0 to (arr.length-1)){
      arr(i) = Integer.valueOf(Random.nextInt(num))
    }
    arr
  }
  /**
   * 1.返回的结果是一个可变数组 ArrayBuffer
   * 2.在找到结果时,向左边扫描,向右边扫描[条件]
   * 3.找到结果后,就加入到 ArrayBuffer
   * @param arr
   * @param left
   * @param right
   * @param findValue
   * @return
   */
  def binarySearch2(arr: Array[Int], left: Int, right: Int, findValue: Int): ArrayBuffer[Int] = {
    if (left > right){
      return ArrayBuffer()
    }

    val midIndex = (left + right)/2
    val midValue = arr(midIndex)
    if (midValue > findValue){
      //向左递归查询
      binarySearch2(arr, left, midIndex-1, findValue)
    }else if(midValue < findValue){
      binarySearch2(arr, midIndex+1, right, findValue)
    }else{
      println("midIndex:"+midIndex)
      //定义一个可变数组
      val resArr: ArrayBuffer[Int] = ArrayBuffer[Int]()
      //向左扫描
      var tmp = midIndex - 1
      import scala.util.control.Breaks._
      breakable{
        while (true){
          if (tmp < 0 || arr(tmp) != findValue){
            break()
          }
          if (arr(tmp) == findValue){
            resArr.append(tmp)
          }
          tmp -= 1
        }
      }
      //将这中间索引加入
      resArr.append(midIndex)
      //向右扫描
      tmp = midIndex + 1
      breakable{
        while (true){
          if (tmp > arr.length || arr(tmp) != findValue){
            break()
          }
          if (arr(tmp) == findValue){
            resArr.append(tmp)
          }
          tmp += 1
        }
      }
      return resArr
    }
  }

  /**
   * 返回找到的索引
   * @param arr
   * @param left
   * @param right
   * @param findValue
   * @return
   */
  def binarySearch(arr: Array[Int], left: Int, right: Int, findValue: Int): Int = {
    if (left > right){ //递归退出条件,找不到
      return -1
    }
    val midIndex = (left + right)/2
    val midValue = arr(midIndex)
    if (midValue > findValue){
      //向左递归查找
      binarySearch(arr,left,midIndex-1,findValue)
    }else if(midValue < findValue){
      //向右递归查询
      binarySearch(arr,midIndex+1,right,findValue)
    }else{
      return midIndex
    }
  }
}
